In computer graphics, images are displayed on a screen by a discrete grid of pixels. Each pixel represents a dot on the screen. Precisely defined geometric primitives from the continuous object space, like triangles, which are to be displayed on the screen thus have to be rasterized to pixel values. This process involves finding the pixels that are at least partially covered by the primitive and defining the color of the pixels. If a pixel is only partly covered by a primitive, a special approach is required for determining an appropriate color of the pixel. Since in this case, the pixel has at least two primitives that cover it, the color of the pixel has to be an interpolation of the colors of the primitives in the area of the continuous object space represented by this pixel. If this process is not carried out properly, the resulting image suffers from aliasing.
The aliasing phenomenon thus results from the masquerading of high spatial frequencies of the object space as low frequencies in the reconstructed image of the object space on the screen. The aliasing phenomenon creates undesirable visual artifacts known as “jaggies” or “staircasing” effect for the edges of the primitive, resulting in imprecise edges, as “popping” effect for very small primitives which are moving across the screen, or as a “flickering” of the presented image.
In order eliminate the aliasing phenomenon to a certain extent, antialiasing techniques are employed. It is to be noted that a total elimination is not theoretically possible.
Antialiasing techniques are essential for high-quality graphics, and they are endorsed by technical standards like OpenGL and DirectX-Direct3D® by Microsoft®. Antialiasing is of particular importance for products including 3D (three-dimensional) graphics and having a “mid-size” display, i.e. a display resolution less than e.g. VGA (Video Graphics Array) but more than QQVGA (Quarter Quarter VGA). Moreover, an efficient and low-power implementation of antialiasing in a display larger than QQVGA typically requires a hardware acceleration. This is important, for instance, for mobile devices.
The causes of aliasing in computer generated imagery are well known from the signal sampling theory and may be broken into two components. The first component is an aliasing due to inadequate sampling of the geometrical primitive from the continuous object space. The second component is an aliasing due to an incorrect or inadequate reconstruction of the displayed image from the generated samples.
While many antialiasing techniques have been proposed, there are no practical effective solutions to succeed in removing both aliasing components causes at once. Therefore, the practical schemes for antialiasing can be classified in pre- and post-filtering methods.
In the post-filtering antialiasing methods, which are also referred to as supersampling antialiasing methods, the geometric primitives in the continuous object space are point sampled at a higher rate than can be displayed, i.e. with multiple samples per pixel. These samples are then numerically filtered by a discrete digital filter for a resampling at the display resolution. The post-filtering hardware algorithms have increased computation and storage costs due to the multiple sample approach. Moreover, they result in certain situations in image artifacts due to the inadequate sampling rate, since the continuous object space often contains infinite spatial frequencies.
The pre-filtering antialiasing methods, which are also referred to as area sampling antialiasing methods, generate displayed images of a higher quality involving potentially lower hardware costs than post-filtering methods by storing only one sample per pixel. The pre-filtering antialiasing methods remove the high frequency components that would produce aliasing from the image before display by performing a low-pass filtering in a pre-filter stage. The bandwidth limited image is then point sampled at the display resolution to produce images with reduced aliasing. The pre-filtering of a geometric primitive is performed by determining pixel coverage values that are used to weight or smooth pixel colors computed during the sampling. Practical schemes of antialiasing with pre-filtering rely heavily on pre-computed coverage mask lookup tables. Those tables are indexed by parameters that contain information about the distance from the pixel center to the edge of the geometrical primitive, information about the slope of the edge, and information on the possible orientation of the edges. To each index, a coverage mask is associated, which gives an information on the extent to which the pixel is covered by the primitive and which thus allows to weight the pixel colors accordingly.
The antialiasing with pre-filtering is performed during a primitive rasterization time. Simply speaking, the primitive rasterization is the conversion through interpolation from the description of the primitive with two-dimensional vertices in the continuous object space into a sequence of properly shaded pixels on the display that belong to the interior and to the boundary edges of the primitive. If a pixel is found to lie on the border of the primitive, the antialiasing is performed at this time by weighting the color of the pixel with the coverage value of the pixel, in order to smooth the edge. Therefore, the method chosen for primitive rasterization will impose limitations on the type of a pre-filtering antialiasing algorithm that can be efficiently implemented in hardware in conjunction with the rasterization engine.
For illustration, different hardware solutions for rasterization approaches and suitable antialiasing schemes based on pre-filtering will be described in the following. The geometric primitive to be displayed is assumed to be a triangle.
A first type of solution is given by the traditional triangle rasterization and antialiasing.
A traditional triangle rasterization, which is also referred to as triangle scan-conversion, is typically performed by an algorithm consisting of an edge-walking interpolation phase followed by a span interpolation phase in its inner loop. During the edge-walking phase, the triangle is scanned vertically from top to bottom, sequentially delivering for every intercepted display scan-line the triangle boundaries along the two edges visited at a particular time. The triangle boundaries constitute the start and the end of the span interpolation phase. During the edge-walking phase, the edge interpolation is performed using the Bresenham's line algorithm. In Bresenham's line algorithm, the sign bit of a control parameter, which can be computed incrementally, determines the respective next pixel that constitutes the best approximation for the ideal line that has to be drawn by the algorithm. The respectively determined next pixel is output on the screen as part of the drawn line.
Hardware antialiasing algorithms with pre-filtering that are working in conjunction with this traditional triangle scan conversion method have focused on modifying the Bresenham's line algorithm to incorporate an area sampling.
M. L. V. Pitteway and D. Watkinson, for example, propose in the document “Bresenham's Algorithm with Grey Scale”, Communications of the ACM, vol. 23, no. 11, pp. 625–626, November 1980, modifications which allow to interpret the control parameter value as a distance measure from the pixel drawn as part of the rasterized line to the ideal line, and to use this control parameter value to weight the color of the pixel that will be displayed. The main drawback of this approach relates to the fact that it cannot handle line ends properly.
Another version of the Bresenham's line algorithm with antialiasing capabilities that can be used to smooth triangle's edges has been described by S. Gupta and R. F. Sproull in the document “Filtering Edges for Gray-Scale Displays”, Computer Graphics (SIGGRAPH 81 Conference Proceedings), vol. 15, no. 3, pp. 1–5, August 1981. Here, the ideal line is convolved with a circularly symmetric filter. The convolution operation is implemented with a lookup table, which is indexed by the perpendicular distance from the pixel center to the line center. Analytic expressions for line ends are again difficult to derive, and a separate, more complex indexing scheme is required for that with less precise two-dimensional lookup tables. The computational complexity increases further, when the antialiasing of the triangle's vertices, i.e. of the points where two line ends will intersect, or the antialiasing of triangles smaller than a pixel, i.e. where multiple line ends and vertices exist, are considered making the traditional approach of rasterization less attractive when used in conjunction with the antialiasing algorithms based on pre-filtering.
It is a drawback of the antialiasing algorithms with pre-filtering based on the traditional rasterization method that it is difficult to achieve an accurate antialiasing of the triangle corners and that it is computationally expensive. It is also a drawback of this approach that the triangle traversal order is imposed by the scan conversion algorithm. The triangle is scanned vertically from top to bottom, and for each generated span, all fragments between the span ends are interpolated before the fragments on other spans can be generated. This makes it very difficult to generate several fragments in parallel in a random order and it makes implementations impossible that generate fragments in a tile rasterization order. Several studies of texture caches have shown the benefits of using a tile rasterization order, in which the screen is tiled into rectangles that are related to the size of the texture cache. All fragments within one tile are generated before any fragments within another tile. Similarly, most frame buffers physically tile the screen into rectangular pages, and tiled rasterization that respects these page boundaries allows for fewer page crossings that can be more efficiently prefetched. The traditional rasterization methods are not capable to make efficient usage of such hardware organizations.
A second type of solution for rasterization and antialiasing based on pre-filtering is given by a triangle rasterization with edge functions and antialiasing.
In this type of solution, the triangle rasterization is based on an algebraic representation of the edges of the triangle. The edge of a triangle can be represented as a vector between its respective vertices, in case respectively one vertex is considered as the source and another vertex as the sink of the vector. This is illustrated in FIG. 1a, in which one vertex of a triangle edge is shown as a first dot at a position (xA,yA) in a Cartesian coordinate system, and in which another vertex of a triangle edge is shown as a second dot at a position (xA+Δx, yA+Δy) in the Cartesian coordinate system. Δx represents the distance in x-direction between the first dot and the second dot, while Δy represents the distance in y-direction between the first dot and the second dot. An arrow V connecting the first dot with the second dot constitutes the vector which represents the triangle edge. The edge is thus defined by a vector starting at point (xA,yA) and having the slope Δy/Δx.
When proceeding from such an edge vector, it can be detected whether a current rasterization position (xM,yM) in the screen space lies in one of the half-planes “left side” or “right side” delimited by the edge vector V or exactly on the edge vector V. The detection process involves the computation of the cross-product of the edge vector V with a vector formed by the edge vector's source (xA,yA) and the current rasterization position (xM,yM). This cross-product can be expressed for any arbitrary pixel position (x,y) on the screen as an analytical function, called the edge function, with the unknowns (x,y). If the result of an evaluation of the edge function at the current rasterization position (xM,yM) is zero, the position (xM,yM) lies exactly on the edge defined by edge vector V. Otherwise, depending on the sign of the evaluation's result, the position (xM,yM) lies in one of the half-planes delimited by the edge vector V.
When considering a triangle described by its clockwise or counter-clockwise oriented edge vectors, a position belongs to the interior of the triangle, if all its edge functions computed for this position and the three edge vectors have the same sign. This is illustrated in FIG. 1b for a triangle having the vertices A, B and C. The interior of the triangle is formed by the union of the right sides of the oriented edges AB, BC and CA represented by a respective edge vector V1, V2 and V3. A plus sign is associated to the interior of the triangle and a minus sign is associated to the planes delimited by the edge vector V1, V2 and V3 and lying outside of the triangle. The values for the edge functions are used as a “stencil” that allows to modify the color of a pixel only if it is interior to the triangle. Thus, the process of rasterizing the triangle can then be reduced to an algorithm that traverses an arbitrary area that includes the interior of the triangle, and that does not strictly follow the outline of the triangle as in the case of the traditional scan conversion rasterization method.
Additionally, if the edge function is properly normalized, its evaluation yields the distance from the respective edge vector to the pixel position (x,y), and this distance can be used in determining the coverage of the pixel at position (x,y) by the triangle's edge. This means that the normalized edge function can be employed for both, rasterization and antialiasing.
The operating principle of an antialiasing algorithm with edge functions is illustrated in more detail in FIGS. 2a, 2b and 2c. 
FIG. 2a illustrates a 16-bit coverage mask encoding scheme. On the left hand side of FIG. 2a, the sequence of the 16 bits of the coverage or subpixel mask is represented by a sequence of 16 squares m0–m15. Each of the bits represents a binary value for a subpixel of a two-dimensional 4×4 grid of subpixels. A corresponding 4×4 grid 10 of subpixels, which are associated to the area of a pixel, is shown on the right hand side of FIG. 2a. Each of the subpixels can be individually lit and unlit by setting the corresponding bit m0–m15 accordingly. In hardware implementations for antialiasing with normalized edge functions, such pictorial representations of the pixel coverage coded in coverage masks are pre-computed for various distances of an edge to the pixel center and various angles of an edge. The pre-computed coverage masks are stored in a coverage mask lookup table.
FIG. 2b illustrates the fetching of a stored coverage mask from a lookup table. On the left hand side of FIG. 2b, the area 11 of a pixel on a screen is depicted, with an edge vector V passing through this area 11. In the middle of FIG. 2b, a look up table LUT 12 is depicted, and on the right hand side of FIG. 2b, a coverage mask 13 is depicted in form of a 4×4 grid of subpixels. During rasterization, the normalized edge function computed for the current rasterization position (xM,yM) is interpreted as a distance d of the edge vector V from the pixel center M. The distance d is used together with the edge slope α as a lookup table address to fetch the 16-bit coverage mask 13 of the current rasterization position for that edge. In the depicted coverage mask 13, black squares represent a bit value of “1” of a respective subpixel, while white squares represent a bit value of “0” of a respective subpixel.
FIG. 2c illustrates the determination of a final coverage value for a pixel using box filtering by ANDing the coverage masks for three edge vectors of a triangle. A first square 14 represents the pixel area which is partly covered by a triangle 15. The table lookup described with reference to FIG. 2b is performed for all the three edges of the triangle 15, resulting in three distinct coverage masks 16, 17 and 18. Each of the coverage masks 16, 17 and 18 is represented in FIG. 2c in form of a 4×4 grid of subpixels. The three resulting coverage masks 16, 17 and 18 are then logically combined by an AND operation to produce a final coverage mask 19. The final coverage mask 19 represents the extent to which the pixel at the current rasterization position (xM, yM) is covered by the triangle. From the number of lit subpixels out of the total number of subpixels represented in the final coverage mask 19, the fraction of the pixel covered by the triangle can be computed. In the presented example, 6 of the 16 bits have a value of “1” and are thus considered to be lit, which results in a coverage value of 6/16.
The resulting coverage value is used to modulate the color of the pixel, i.e. the transparency or the alpha value, which is computed by interpolation for the current rasterization position (xM,yM)
The scheme presented in FIG. 2c is equivalent with a process of pre-filtering having a box-shaped filter kernel.
The rasterization and antialiasing method presented with reference to FIGS. 2a to 2c was adopted by H. Fuchs et al. in document “Fast Spheres, Shadows, Textures, Transparencies, and Image Enhancements in Pixel-Planes”, Computer Graphics (SIGGRAPH 85 Conference Proceedings), vol. 19, no. 3, pp. 111–120, July 1985 in Pixel Planes. Pixel Planes is a logic-enhanced memory system for raster graphics and imaging with a high degree of generality. Using a global computing structure, more specifically a linear expression tree evaluated in a bit-sequential order, the system can evaluate linear expressions like edge functions for every pixel position (x,y) on the screen in parallel. The coverage mask for an edge is fetched by indexing a pre-computed coverage mask lookup table with the normalized edge function value and one of the coefficients of the edge function that gives information about the slope of the edge. The system is extremely large, since it provides a separate processor for every pixel in the display. Each of the pixel processors contains an 1-bit ALU (arithmetic-logic unit) and a small amount of memory. Pixel-Planes 4, a full-scale system completed in 1986, contained 262144 processors forming a 512-by-512 pixel image.
In the document “A Parallel Algorithm for Polygon Rasterization”, Computer Graphics (SIGGRAPH 88 Conference Proceedings), vol. 22, no. 4, pp. 17–20, August 1988, by J. Pineda, an effective expression for the cross-product of the vectors was embodied in the edge function formulation, emphasizing that iterative techniques, with only one addition per pixel, can be used for neighboring pixels to evaluate the edge function. For an edge vector defined by the points (xA,yA) and (xA+Δx,yA+Δy), as presented in FIG. 1a, this edge function for a certain point M at position (xM,yM), e.g. the center M of a pixel, is expressed as:E(xM,yM)=(xM−xA)·Δy−(yM−yA)·Δx  (1)
The iterative property is well suited for a low-cost rasterizer, which steps through a triangle generating one or a group of fragments at each step. By this new edge function formulation, the method of triangle rasterization of the second presented type of solution is more effective in performance and hardware costs than the traditional rasterization method presented above as first type of solution.
An antialiasing algorithm using coverage masks which are based on the edge function formulation from the above cited document “A Parallel Algorithm for Polygon Rasterization” has been presented by A. Schilling in the document “A New Simple and Efficient Antialiasing with Subpixel Masks”, Computer Graphics (SIGGRAPH 91 Conference Proceedings), vol. 25, no. 4, pp. 133–141, July 1991. Each pixel is represented as a matrix of 4×4 subpixels and the associated coverage mask is encoded as a 16-bit word as presented in FIG. 2a. A new formulation for the distance of the edge vector to the pixel center M with a good accuracy based on the edge function normalization with an L1-norm is proposed, which avoids the sum of squares and the square root computation involved by the Euclidian distance evaluation:                                                                                           d                  L1                                ⁡                                  (                  M                  )                                            =                                                E                  ⁡                                      (                                                                  x                        M                                            ,                                              y                        M                                                              )                                                                                                                                  Δ                      ⁢                                                                                          ⁢                      x                                                                            +                                                                                Δ                      ⁢                                                                                          ⁢                      y                                                                                                                                                                  =                                                                    (                                                                  x                        M                                            -                                              x                        A                                                              )                                    ·                                                            Δ                      ⁢                                                                                          ⁢                      y                                                                                                                                        Δ                          ⁢                                                                                                          ⁢                          x                                                                                            +                                                                                                Δ                          ⁢                                                                                                          ⁢                          y                                                                                                                                            -                                                      (                                                                  y                        M                                            -                                              y                        A                                                              )                                    ·                                                            Δ                      ⁢                                                                                          ⁢                      x                                                                                                                                        Δ                          ⁢                                                                                                          ⁢                          x                                                                                            +                                                                                                Δ                          ⁢                                                                                                          ⁢                          y                                                                                                                                                                                                                    =                                                                                          (                                                                        x                          M                                                -                                                  x                          A                                                                    )                                        ·                    d                                    ⁢                                                                          ⁢                                                            e                      x                                        ⁡                                          (                      α                      )                                                                      -                                                                            (                                                                        y                          M                                                -                                                  y                          A                                                                    )                                        ·                    d                                    ⁢                                                                          ⁢                                                            e                      y                                        ⁡                                          (                      α                      )                                                                                                                                              =                                                sgn                  ⁡                                      (                                                                  d                        L1                                            ⁡                                              (                        M                        )                                                              )                                                  ·                d                ·                                                                                                    Δ                        ⁢                                                                                                  ⁢                                                  x                          2                                                                    +                                              Δ                        ⁢                                                                                                  ⁢                                                  y                          2                                                                                                                                                                                              Δ                        ⁢                                                                                                  ⁢                        x                                                                                    +                                                                                        Δ                        ⁢                                                                                                  ⁢                        y                                                                                                                                                                                          =                                                sgn                  ⁡                                      (                                                                  d                        L1                                            ⁡                                              (                        M                        )                                                              )                                                  ·                                  f                  ⁡                                      (                                          d                      ,                      α                                        )                                                                                                          (        2        )            
The L1-norm distance dL1(M) and the parameters dex(α) and dey(α) are functions of the Euclidian distance d and the angle α presented in FIG. 2b. 
Any edge vector in the 2D (two dimensional) space at any Euclidian distance d from the pixel center M and at any angle α can be identified unambiguously using the parameters dL1(M), dex(α) and sgn(dey(α)). Since the angle α is difficult to compute per se, the index used to fetch the coverage masks from the coverage mask lookup table can therefore be composed of the parameters dL1(M), dex(α), and sgn(dey(α)). In a practical implementation, only the coverage masks for partially covered pixels have to be stored in the coverage mask lookup table, imposing the range for the L1-norm distance to be dL1(M)ε(−0.5,+0.5).
Outside this range, the pixel is totally covered or totally uncovered by the triangle edge, and the coverage mask can be assigned implicitly to comprise subpixels which are all set or unset, depending on the sign of the L1-norm distance dL1(M). The ranges for the other parameters that depend on the angle α of the edge vector alone are dex(α)ε[−1,+1] and sgn(dey(α))ε{−1,+1}.
In order to limit the coverage masks lookup table to a reasonable size, the edge vectors can be grouped in edge vector classes, and only several representative classes are stored in the coverage masks lookup table. An edge vector class is defined in this context as a set of all the edge vectors with the same dex(α) and sgn(dey(α)) values, but with distinct dL1(M) values, the values lying in the above indicated ranges. Hence, an edge vector class contains all the edge vectors with the same slope that may partially cover a pixel.
With a subpixel lattice of 4×4, only 32 representative edge vector classes from all four quadrants of the plane have to be stored, as illustrated in FIGS. 3a and 3b. 
FIG. 3a shows an enlarged 7×7 grid of subpixels, in which the subpixels are shown as dotted squares. The 4×4 subpixels in the right upper corner of the enlarged grid represent a first quadrant for vectors of a first orientation. The 4×4 subpixels in the left upper corner of the enlarged grid represent a second quadrant for vectors of a second orientation. The 4×4 subpixels in the left lower corner of the enlarged grid represent a third quadrant for vectors of a third orientation. The 4×4 subpixels in the right lower corner of the enlarged grid represent a fourth quadrant for vectors of a fourth orientation. The middle row and the middle column of subpixels thus belong in common to respectively two of the 4×4 grids of subpixels, while the central subpixel of the enlarged grid belongs in common to all four of the 4×4 grids of subpixels. Further, 32 representative edge vector classes represented through a respective sample edge vector per class are shown, all vectors having their source at the central subpixel of the enlarged grid. Eight of the sample edge vectors are labeled A to H, respectively. The 32 representative edge vector classes were chosen by drawing all possible edge vectors that are passing through the subpixel centers of a pixel when proceeding from the center of the corner subpixels.
FIG. 3b shows the edge vectors belonging to the representative edge vector class B, i.e. all edge vectors having the same slope as the edge vector B of FIG. 3a and having one of 17 possible distances dL1(M) to the center of a 4×4 grid 20 of subpixel.
Then, the coverage mask that will be stored corresponding to an index given by the parameters dL1(M), dex(α) and sgn(dey(α)) of an edge vector is computed by ensuring that the number of subpixels lit in the coverage mask is correct plus or minus ½ of a subpixel, based on the exact covered area of the pixel.
The index for an entry in the coverage masks lookup table is obtained by concatenating the truncated L1-norm distance dL1(M) to 5 msb (most significant bits) including the sign bit, the truncated parameter dex(α) to 5 msb including the sign bit, and one bit for the sign of the parameter dey(α). Nevertheless, additional redundancy has to be built in the table. On the one hand, it has to be ensured that two adjacent triangles, both front-facing or both back-facing, always complement each other, i.e. a total coverage of more than 4×4 subpixels per pixel is impossible. Adjacent primitives which occupy other than 100% of the pixel lead to color errors like edge cracking. On the other hand, the biasing of a rounding scheme based on truncation towards −∞ has to be counteracted in a two's complement number system. This increases the coverage masks lookup table size to 8000 words of 16 bits comprising 8000 coverage masks.
In contrast to the antialiasing methods with pre-filtering based on the traditional rasterization method, the antialiasing methods with pre-filtering based on normalized edge functions perform the antialiasing of the edge intersections with accuracy. Further, they do not favor any particular order of triangle traversal, which makes them well-suited for a tile rasterization order. However, their hardware implementation, which is based on coverage mask lookup tables, is often inefficient. The coverage mask lookup tables contain thousands of coverage masks that consume a considerable chip area. This leads to a coverage mask lookup table time-sharing access approach and prevents an employment of low-power techniques that capitalize on parallel computation to reduce the activity factor inside the antialiasing circuitry. Large lookup tables are of particular disadvantage for mobile devices. Moreover, the large coverage mask lookup table content combined with the mechanism used to fetch the coverage mask during rasterization is a source of inaccuracies, which has to be minimized by additional measures.
A further document dealing with pre-filter antialiasing techniques is U.S. Pat. No. 5,742,277, which discloses a method where the antialiasing of an internal edge is performed right before display to avoid the problems that arise if this antialiasing is carried out in the blender. This method makes use of the coverage value to form the color of the pixel, but the actual formation of this coverage value is not described. International patent application WO 99/45502 A1 describes a method for creating a coverage alpha value by subsampling the pixels. U.S. Pat. No. 5,369,739 describes a subsampling that can be used for determining the coverage value.